﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Util.Data
{
    /// <summary>
    /// Represents a specialized dictionary where keys are grouped in ranges
    /// where keys in the same range map to the same value. If two contiguous
    /// ranges map to the same value, they are automatically combined.
    /// </summary>
    /// <typeparam name="TKey"></typeparam>
    /// <typeparam name="TValue"></typeparam>
    /// <remarks>
    /// Ideally, we should use a binary search tree as the underlying data
    /// structure. However, for simplicity, we use a plain sorted array for
    /// the moment.
    /// </remarks>
    public class RangeDictionary<TKey, TValue> :
        IDictionary<Range<TKey>, TValue>
        where TKey : IComparable<TKey>
    {
        readonly List<KeyValuePair<Range<TKey>, TValue>> items;

        readonly List<Range<TKey>> keys;
        readonly List<TValue> values;

        /// <summary>
        /// Creates a range dictionary with the given lower-bound and
        /// upper-bound of keys.
        /// </summary>
        /// <param name="keyLowerBound"></param>
        /// <param name="keyUpperBound"></param>
        public RangeDictionary()
        {
            this.keys = new List<Range<TKey>>();
            this.values = new List<TValue>();
        }

        /// <summary>
        /// Gets the number of disjoint key-value mappings in the dictionary.
        /// </summary>
        public int Count
        {
            get { return values.Count; }
        }

        public IEnumerator<KeyValuePair<Range<TKey>, TValue>> GetEnumerator()
        {
            throw new NotSupportedException();
            //return chunks.GetEnumerator();
            //return new Enumerator(this, -1);
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

#if false
        public IEnumerator<KeyValuePair<Range<TKey>, TValue>> FindLowerBound(TKey key)
        {
            throw new NotImplementedException();
        }

        struct Enumerator : IEnumerator<KeyValuePair<Range<TKey>, TValue>>
        {
            RangeDictionary<TKey, TValue> dict;
            int index;

            public Enumerator(RangeDictionary<TKey, TValue> dict, int index)
            {
                this.dict = dict;
                this.index = index;
            }

            public void Dispose()
            {
            }

            public void Reset()
            {
                index = -1;
            }

            public bool MoveNext()
            {
                if (++index < dict.chunks.Count)
                    return true;
                else
                    return false;
            }

            public KeyValuePair<Range<TKey>, TValue> Current
            {
                get
                {
                    if (index < 0 || index >= dict.chunks.Count)
                    {
                        throw new InvalidOperationException("There is no current element.");
                    }
                    return dict.chunks[index];
                }
            }

            object System.Collections.IEnumerator.Current
            {
                get { return Current; }
            }
        }
#endif

        /// <summary>
        /// Finds the index of the smallest range that intersects the given
        /// range. If none exists, finds the smallest range that comes after
        /// the given range.
        /// </summary>
        /// <param name="range"></param>
        /// <returns></returns>
        private int BinarySearch(Range<TKey> range)
        {
            int k = keys.BinarySearch(range, CompareRanges);
            //while (k > 0 && CompareFixupWithOffset(fixups[k - 1], offset) == 0)
            //    k--;
            return k;
        }

        /// <summary>
        /// Compares two ranges and returns 0 if they intersect, or +/-1 if
        /// one is strictly before the other.
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        private static int CompareRanges(Range<TKey> a, Range<TKey> b)
        {
            if (a.Begin.CompareTo(b.End) >= 0)
                return 1;
            else if (b.Begin.CompareTo(a.End) >= 0)
                return -1;
            else
                return 0;
        }

        public bool TryGetValue(Range<TKey> key, out TValue value)
        {
            int k = BinarySearch(key);
            if (k >= 0)
            {
                if (!keys[k].IsSupersetOf(key))
                {
                    throw new ArgumentException("Partial overlapping.");
                }
                value = values[k];
                return true;
            }
            else
            {
                value = default(TValue);
                return false;
            }
        }

        public TValue GetValueOrDefault(Range<TKey> key)
        {
            TValue value;
            if (TryGetValue(key, out value))
                return value;
            else
                return default(TValue);
        }

        public void Add(Range<TKey> key, TValue value)
        {
            // Find where to insert the element.
            int k = BinarySearch(key);

            // We do not allow overlapping keys.
            if (k >= 0)
                throw new ArgumentException("Overlapping keys are not allowed.", "key");

            // Now k points to the immediate range after 'key'.
            k = ~k;

            // Check if 'key' connects its preceding and following ranges.
            bool connectsPrev = (k > 0) &&
                                (keys[k - 1].End.CompareTo(key.Begin) == 0) &&
                                values[k - 1].Equals(value);
            bool connectsNext = (k < keys.Count) &&
                                (keys[k].Begin.CompareTo(key.End) == 0) &&
                                values[k].Equals(value);

            if (connectsPrev && connectsNext)
            {
                keys[k - 1] = new Range<TKey>(keys[k - 1].Begin, keys[k].End);
                keys.RemoveAt(k);
                values.RemoveAt(k);
            }
            else if (connectsPrev)
            {
                keys[k - 1] = new Range<TKey>(keys[k - 1].Begin, key.End);
            }
            else if (connectsNext)
            {
                keys[k] = new Range<TKey>(key.Begin, keys[k].End);
            }
            else
            {
                keys.Insert(k, key);
                values.Insert(k, value);
            }
        }

        public bool Remove(Range<TKey> key)
        {
            int k = BinarySearch(key);
            if (k < 0)
                return false;
            if (!keys[k].IsSupersetOf(key))
                throw new ArgumentException("Partial Overlapping.");

            bool matchBegin = keys[k].Begin.CompareTo(key.Begin) == 0;
            bool matchEnd = keys[k].End.CompareTo(key.End) == 0;
            if (matchBegin && matchEnd)
            {
                keys.RemoveAt(k);
                values.RemoveAt(k);
            }
            else if (matchBegin)
            {
                keys[k] = new Range<TKey>(key.End, keys[k].End);
            }
            else if (matchEnd)
            {
                keys[k] = new Range<TKey>(keys[k].Begin, key.Begin);
            }
            else
            {
                throw new NotImplementedException();
            }

            return true;
        }

        public bool ContainsKey(Range<TKey> key)
        {
            throw new NotImplementedException();
        }

        public ICollection<Range<TKey>> Keys
        {
            get { throw new NotImplementedException(); }
        }

        public ICollection<TValue> Values
        {
            get { throw new NotImplementedException(); }
        }

        public TValue this[Range<TKey> key]
        {
            get
            {
                throw new NotImplementedException();
            }
            set
            {
                throw new NotImplementedException();
            }
        }

        #region ICollection Interface Implementation

        public void Add(KeyValuePair<Range<TKey>, TValue> item)
        {
            throw new NotImplementedException();
        }

        public void Clear()
        {
            throw new NotImplementedException();
        }

        public bool Contains(KeyValuePair<Range<TKey>, TValue> item)
        {
            throw new NotImplementedException();
        }

        public void CopyTo(KeyValuePair<Range<TKey>, TValue>[] array, int arrayIndex)
        {
            throw new NotImplementedException();
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        public bool Remove(KeyValuePair<Range<TKey>, TValue> item)
        {
            throw new NotImplementedException();
        }

        #endregion
    }
}
